package com.hy.stack;

import java.util.*;

public class TopKFrequent {


    /**
     * 347.前 K 个高频元素
     * 力扣题目链接
     * 给定一个非空的整数数组，返回其中出现频率前 k 高的元素。
     *
     * 示例 1:
     * 输入: nums = [1,1,1,2,2,3], k = 2
     * 输出: [1,2]
     *
     * 思路
     * 这道题目主要涉及到如下三块内容：
     *
     * 要统计元素出现频率
     * 对频率排序
     * 找出前K个高频元素
     * 首先统计元素出现的频率，这一类的问题可以使用map来进行统计。
     *
     * 然后是对频率进行排序，这里我们可以使用一种 容器适配器就是优先级队列。
     *
     * @param k
     * @return
     */
    public static int [] topKFrequent(int [] nums,int k){
        int [] res = new int[k];
        Map<Integer, Integer> map = new HashMap<>();
        // 将数据存入 map中
        for (int num : nums) {
            map.put(num,map.getOrDefault(num,0)+1);
        }

        Set<Map.Entry<Integer, Integer>> entries = map.entrySet();
        // 根据map的value值正序排，相当于一个小顶堆
        // 基于最小堆实现
        PriorityQueue<Map.Entry<Integer,Integer>> queue = new PriorityQueue<>((o1,o2) -> o1.getValue() - o2.getValue());
        for (Map.Entry<Integer, Integer> entry : entries) {
            queue.offer(entry);
            if (queue.size() > k){
                queue.poll();
            }
        }
        for (int i = k - 1; i >= 0; i--) {
            res[i] = queue.poll().getKey();
        }

        return res;
    }

    public static void main(String[] args) {
        int [] num = {1,1,1,2,2,3,3,5,5,5};
        int k = 3;

        System.out.println("res: "+ Arrays.toString(topKFrequent(num, 3)));

    }
}
